<!DOCTYPE html>
<html manifest="cache.appcache">
  <head>
    <meta charset="utf-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=Edge;chrome=1" />
    <title>[Concurrency is not Parallelism (it&#39;s better)]</title>
    <link href="http://fonts.googleapis.com/css?family=Droid+Sans|Droid+Sans+Mono" rel="stylesheet" type="text/css" />
    <link id="prettify-link" href="src/prettify/prettify.css" rel="stylesheet" disabled />
    <link href="css/default.css" class="theme" rel="stylesheet" media="screen"  />
    <link href="css/common.css" rel="stylesheet" media="screen" />
  </head>
  <body>
    <nav id="helpers">
      <button title="Previous slide" id="nav-prev" class="nav-prev">⇽</button> 
      <button title="Jump to a random slide" id="slide-no">5</button> 
      <button title="Next slide" id="nav-next" class="nav-next">⇾</button>
      <menu>
        <button type="checkbox" data-command="toc" title="Table of Contents" class="toc">TOC</button>
        <button type="checkbox" data-command="notes" title="View Slide Notes">✏</button>
        <button type="checkbox" data-command="source" title="View slide source">↻</button>
        <button type="checkbox" data-command="help" title="View Help">?</button>
      </menu>
    </nav>
    <div class="presentation">
      <div id="presentation-counter">Loading...</div>
      <div class="slides">
        <div class="slide" id="landing-slide">
          <style>
            #landing-slide p {
              font-size: 35px;
            }
          </style>
          <section class="middle">
            <p>This presentation is an HTML5 web site</p>
            <p>Press <span id="left-init-key" class="key">&rarr;</span> key to advance.</p>
          </section>

          <aside class="note">
            <section>
              Welcome! (This field is for presenter notes and commentary.)
            </section>
          </aside> 
        </div>

        <div class="slide" id="controls-slide">
          <header>Controls</header>
          <style>
            #controls-slide li, #controls-slide p {
              font-size: 32px;
            }
            #controls-slide .key {
              bottom: 2px;
            }
          </style>
          <section>
            <ul>
              <li><span class="key">&larr;</span> and <span class="key">&rarr;</span> to move around.</li>
              <li><span class="key">Ctrl/Command</span> and <span class="key">+</span> or <span class="key">-</span> to zoom.</li>
              <li><span class="key">S</span> to view page source.</li>
              <li><span class="key">N</span> to toggle speaker notes.</li>
              <li><span class="key">3</span> to toggle 3D effect.</li>
              <li><span class="key">0</span> to toggle help.</li>
            </ul>
          </section>
        </div>

        <div class="slide" id="hello">
          <section class="middle">
            <hgroup><img src="http://golang.org/doc/gopher/bumper640x360.png"></hgroup>
          </section>
        </div>

        <div class="slide" id="title-slide">
          <style>
            #title-slide h1, #title-slide h2 {
              color: black;
            }
            #title-slide h1 {
              font-size: 80px;
            }
            #title-slide h2 {
              font-size: 36px;
            }
          </style>
          <section class="middle">
            <hgroup>
              <h1>
                
                  Concurrency<br>
                
                  is not<br>
                
                  Parallelism<br>
                
                  (it&#39;s better)<br>
                
              </h1>
              <h2>
                Rob Pike<br>r@golang.org<br>Waza<br>Jan 11, 2012<br>
              </h2>
            </hgroup>
          </section>
        </div>

	<!-- start of slide 0 -->
        <div class="slide" id="slide-0">
          <header>The modern world is parallel</header>

          <section>
            <p>
            Multicore.<br>
            
            <br>
            
            Networks.<br>
            
            <br>
            
            Clouds of CPUs.<br>
            
            <br>
            
            Loads of users.<br>
            
            <br>
            
            Our technology should help.<br>
            
            That&#39;s where concurrency comes in.<br>
            
            <br>
            </p>
            



            <p>
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 0 --><!-- start of slide 1 -->
        <div class="slide" id="slide-1">
          <header>Go supports concurrency</header>

          <section>
            <p>
            Go provides:<br>
            </p>
            
            <ul>
            
            <li>concurrent execution (goroutines)</li>
            
            <li>synchronization and messaging (channels)</li>
            
            <li>multi-way concurrent control (select)</li>
            
            </ul>
            



            <p>
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 1 --><!-- start of slide 2 -->
        <div class="slide" id="slide-2">
          <header>Concurrency is cool! Yay parallelism!!</header>

          <section>
            <p>
            NO! A fallacy.<br>
            
            <br>
            
            When Go was announced, many were confused by the distinction.<br>
            
            <br>
            
            &#34;I ran the prime sieve with 4 processors and it got slower!&#34;<br>
            
            <br>
            </p>
            



            <p>
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 2 --><!-- start of slide 3 -->
        <div class="slide" id="slide-3">
          <header>Concurrency</header>

          <section>
            <p>
            Programming as the composition of independently executing processes.<br>
            
            <br>
            
            (Processes in the general sense, not Linux processes. Famously hard to define.)<br>
            
            <br>
            </p>
            



            <p>
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 3 --><!-- start of slide 4 -->
        <div class="slide" id="slide-4">
          <header>Parallelism</header>

          <section>
            <p>
            Programming as the simultaneous execution of (possibly related) computations.<br>
            
            <br>
            </p>
            



            <p>
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 4 --><!-- start of slide 5 -->
        <div class="slide" id="slide-5">
          <header>Concurrency vs. parallelism</header>

          <section>
            <p>
            Concurrency is about dealing with lots of things at once.<br>
            
            <br>
            
            Parallelism is about doing lots of things at once.<br>
            
            <br>
            
            Not the same, but related.<br>
            
            <br>
            
            One is about structure, one is about execution.<br>
            
            <br>
            
            Concurrency provides a way to structure a solution to solve a problem that may (but not necessarily) be parallelizable.<br>
            
            <br>
            </p>
            



            <p>
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 5 --><!-- start of slide 6 -->
        <div class="slide" id="slide-6">
          <header>An analogy</header>

          <section>
            <p>
            Concurrent: Mouse, keyboard, display, and disk drivers.<br>
            
            <br>
            
            Parallel: Vector dot product.<br>
            
            <br>
            </p>
            



            <p>
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 6 --><!-- start of slide 7 -->
        <div class="slide" id="slide-7">
          <header>Concurrency plus communication</header>

          <section>
            <p>
            Concurrency is a way to structure a program by breaking it into pieces that can be executed independently.<br>
            
            <br>
            
            Communication is the means to coordinate the independent executions.<br>
            
            <br>
            
            This is the Go model and (like Erlang and others) it&#39;s based on CSP:<br>
            
            <br>
            
            C. A. R. Hoare: Communicating Sequential Processes (CACM 1978)<br>
            
            <br>
            </p>
            



            <p>
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 7 --><!-- start of slide 8 -->
        <div class="slide" id="slide-8">
          <header>Gophers</header>

          <section>
            <p>
            This is too abstract. Let&#39;s get concrete.<br>
            
            <br>
            </p>
            



            <p>
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 8 --><!-- start of slide 9 -->
        <div class="slide" id="slide-9">
          <header>Our problem</header>

          <section>
            <p>
            Move a pile of obsolete language manuals to the incinerator.<br>
            </p>
            



<img src="concur/gophersimple1.jpg" >

            <p>
            <br>
            
            With only one gopher this will take too long.<br>
            
            <br>
            
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 9 --><!-- start of slide 10 -->
        <div class="slide" id="slide-10">
          <header>More gophers!</header>

          <section>
            <p></p>
            



<img src="concur/gophersimple3.jpg" >

            <p>
            <br>
            
            More gophers are not enough; they need more carts.<br>
            
            <br>
            
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 10 --><!-- start of slide 11 -->
        <div class="slide" id="slide-11">
          <header>More gophers and more carts</header>

          <section>
            <p></p>
            



<img src="concur/gophersimple2.jpg" >

            <p>
            <br>
            
            This will go faster, but there will be bottlenecks at the pile and incinerator.<br>
            
            Also need to synchronize the gophers.<br>
            
            A message (that is, a communication between the gophers) will do.<br>
            
            <br>
            
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 11 --><!-- start of slide 12 -->
        <div class="slide" id="slide-12">
          <header>Double everything</header>

          <section>
            <p>
            Remove the bottleneck; make them really independent.<br>
            </p>
            



<img src="concur/gophersimple4.jpg" >

            <p>
            This will consume input twice as fast.<br>
            
            <br>
            
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 12 --><!-- start of slide 13 -->
        <div class="slide" id="slide-13">
          <header>Concurrent composition</header>

          <section>
            <p></p>
            



<img src="concur/gophersimple4.jpg" >

            <p>
            The concurrent composition of two gopher procedures.<br>
            
            <br>
            
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 13 --><!-- start of slide 14 -->
        <div class="slide" id="slide-14">
          <header>Concurrent composition</header>

          <section>
            <p>
            This design is not automatically parallel!<br>
            
            <br>
            
            What if only one gopher is moving at a time?<br>
            
            Then it&#39;s still concurrent (that&#39;s in the design), just not parallel.<br>
            
            <br>
            
            However, it&#39;s automatically parallelizable!<br>
            
            <br>
            
            Moreover the concurrent composition suggests other models.<br>
            
            <br>
            </p>
            



            <p>
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 14 --><!-- start of slide 15 -->
        <div class="slide" id="slide-15">
          <header>Another design</header>

          <section>
            <p></p>
            



<img src="concur/gophercomplex0.jpg" >

            <p>
            <br>
            
            Three gophers in action, but with likely delays.<br>
            
            Each gopher is an independently executing procedure,<br>
            
            plus coordination (communication).<br>
            
            <br>
            
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 15 --><!-- start of slide 16 -->
        <div class="slide" id="slide-16">
          <header>Finer-grained concurrency</header>

          <section>
            <p>
            Add another gopher procedure to return the empty carts.<br>
            </p>
            



<img src="concur/gophercomplex1.jpg" >

            <p>
            Four gophers in action for better flow, each doing one simple task.<br>
            
            <br>
            
            If we arrange everything right (implausible but not impossible), that&#39;s four times faster than our original one-gopher design.<br>
            
            <br>
            
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 16 --><!-- start of slide 17 -->
        <div class="slide" id="slide-17">
          <header>Observation</header>

          <section>
            <p>
            We improved performance by adding a concurrent procedure to the existing design.<br>
            
            <br>
            
            More gophers doing more work; it runs better.<br>
            
            <br>
            
            This is a deeper insight than mere parallelism.<br>
            
            <br>
            </p>
            



            <p>
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 17 --><!-- start of slide 18 -->
        <div class="slide" id="slide-18">
          <header>Concurrent procedures</header>

          <section>
            <p>
            Four distinct gopher procedures:<br>
            </p>
            
            <ul>
            
            <li>load books onto cart</li>
            
            <li>move cart to incinerator</li>
            
            <li>unload cart into incinerator</li>
            
            <li>return empty cart</li>
            
            </ul>
            



            <p>
            Different concurrent designs enable different ways to parallelize.<br>
            
            <br>
            
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 18 --><!-- start of slide 19 -->
        <div class="slide" id="slide-19">
          <header>More parallelization!</header>

          <section>
            <p>
            We can now parallelize on the other axis; the concurrent design makes it easy. Eight gophers, all busy.<br>
            </p>
            



<img src="concur/gophercomplex2.jpg" >

            <p>
            <br>
            
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 19 --><!-- start of slide 20 -->
        <div class="slide" id="slide-20">
          <header>Or maybe no parallelization at all</header>

          <section>
            <p>
            Keep in mind, even if only one gopher is active at a time (zero parallelism), it&#39;s still a correct and concurrent solution.<br>
            </p>
            



<img src="concur/gophercomplex2.jpg" >

            <p>
            <br>
            
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 20 --><!-- start of slide 21 -->
        <div class="slide" id="slide-21">
          <header>Another design</header>

          <section>
            <p>
            Here&#39;s another way to structure the problem as the concurrent composition of gopher procedures.<br>
            
            <br>
            
            Two gopher procedures, plus a staging pile.<br>
            </p>
            



<img src="concur/gophercomplex3.jpg" >

            <p>
            <br>
            
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 21 --><!-- start of slide 22 -->
        <div class="slide" id="slide-22">
          <header>Parallelize the usual way</header>

          <section>
            <p>
            Run more concurrent procedures to get more throughput.<br>
            </p>
            



<img src="concur/gophercomplex4.jpg" >

            <p>
            <br>
            
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 22 --><!-- start of slide 23 -->
        <div class="slide" id="slide-23">
          <header>Or a different way</header>

          <section>
            <p>
            Bring the staging pile to the multi-gopher concurrent model:<br>
            
            <br>
            </p>
            



<img src="concur/gophercomplex5.jpg" >

            <p>
            <br>
            
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 23 --><!-- start of slide 24 -->
        <div class="slide" id="slide-24">
          <header>Full on optimization</header>

          <section>
            <p>
            Use all our techniques. Sixteen gophers hard at work!<br>
            
            <br>
            </p>
            



<img src="concur/gophercomplex6.jpg" >

            <p>
            <br>
            
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 24 --><!-- start of slide 25 -->
        <div class="slide" id="slide-25">
          <header>Lesson</header>

          <section>
            <p>
            There are many ways to break the processing down.<br>
            
            <br>
            
            That&#39;s concurrent design.<br>
            
            <br>
            
            Once we have the breakdown, parallelization can fall out and correctness is easy.<br>
            
            <br>
            </p>
            



            <p>
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 25 --><!-- start of slide 26 -->
        <div class="slide" id="slide-26">
          <header>Back to Computing</header>

          <section>
            <p>
            In our book transport problem, substitute:<br>
            </p>
            
            <ul>
            
            <li>book pile =&gt; web content</li>
            
            <li>gopher =&gt; CPU</li>
            
            <li>cart =&gt; marshaling, rendering, or networking</li>
            
            <li>incinerator =&gt; proxy, browser, or other consumer</li>
            
            </ul>
            



            <p>
            It becomes a concurrent design for a scalable web service.<br>
            
            Gophers serving web content.<br>
            
            <br>
            
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 26 --><!-- start of slide 27 -->
        <div class="slide" id="slide-27">
          <header>A little background about Go</header>

          <section>
            <p>
            Not the place for a tutorial, just quick highlights.<br>
            
            <br>
            </p>
            



            <p>
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 27 --><!-- start of slide 28 -->
        <div class="slide" id="slide-28">
          <header>Goroutines</header>

          <section>
            <p>
            A goroutine is a function running independently  in the same address space as other goroutines.<br>
            </p>
            


<pre>
<!--{{code "concur/snippets" `/f.runs/`}}
-->f(&#34;hello&#34;, &#34;world&#34;) // f runs; we wait
</pre>

<pre>
<!--{{code "concur/snippets" `/f.starts.running/` `/return/`}}
-->go f(&#34;hello&#34;, &#34;world&#34;) // f starts running
g() // does not wait for f to return
</pre>


            <p>
            <br>
            
            Like launching a function with shell&#39;s &amp; notation.<br>
            
            <br>
            
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 28 --><!-- start of slide 29 -->
        <div class="slide" id="slide-29">
          <header>Goroutines are not threads </header>

          <section>
            <p>
            (They&#39;re a bit like threads, but they&#39;re much cheaper.)<br>
            
            <br>
            
            Goroutines are multiplexed onto OS threads as required.<br>
            
            <br>
            
            When a goroutine blocks, that thread blocks but no other goroutine blocks.<br>
            
            <br>
            </p>
            



            <p>
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 29 --><!-- start of slide 30 -->
        <div class="slide" id="slide-30">
          <header>Channels</header>

          <section>
            <p>
            Channels are typed values that allow goroutines to synchronize and exchange information.<br>
            
            <br>
            </p>
            


<pre>
<!--{{code "concur/snippets" `/make.*chan/` `/completedAt/`}}
-->timerChan := make(chan time.Time)
go func() {
    time.Sleep(deltaT)
    timerChan &lt;- time.Now() // send time on timerChan
}()
// Do something else; when ready, receive.
// Receive will block until timerChan delivers.
// Value sent is other goroutine&#39;s completion time.
completedAt := &lt;-timerChan
</pre>


            <p>
            <br>
            
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 30 --><!-- start of slide 31 -->
        <div class="slide" id="slide-31">
          <header>Select</header>

          <section>
            <p>
            The select statement is like a switch, but the decision is based on ability to communicate rather than equal values.<br>
            
            <br>
            </p>
            


<pre>
<!--{{code "concur/snippets" `/select/` `/}/`}}
-->select {
case v := &lt;-ch1:
    fmt.Println(&#34;channel 1 sends&#34;, v)
case v := &lt;-ch2:
    fmt.Println(&#34;channel 2 sends&#34;, v)
default: // optional
    fmt.Println(&#34;neither channel was ready&#34;)
}
</pre>


            <p>
            <br>
            
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 31 --><!-- start of slide 32 -->
        <div class="slide" id="slide-32">
          <header>Go really supports concurrency</header>

          <section>
            <p>
            Really.<br>
            
            <br>
            
            It&#39;s routine to create thousands of goroutines in one program.<br>
            
            (Once debugged a program after it had created 1.3 million.)<br>
            
            <br>
            
            Stacks start small, but grow and shrink as required.<br>
            
            <br>
            
            Goroutines aren&#39;t free, but they&#39;re very cheap.<br>
            
            <br>
            </p>
            



            <p>
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 32 --><!-- start of slide 33 -->
        <div class="slide" id="slide-33">
          <header>Closures are also part of the story</header>

          <section>
            <p>
            Make some concurrent calculations easier to express.<br>
            
            <br>
            
            They are just local functions.<br>
            
            Here&#39;s a non-concurrent example.<br>
            </p>
            


<pre>
<!--{{code "concur/snippets" `/Compose/` `/sin,/`}}
-->func Compose(f, g func(x float) float)
                  func(x float) float {
     return func(x float) float {
        return f(g(x))
    }
}

print(Compose(sin, cos)(0.5))
</pre>


            <p>
            <br>
            
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 33 --><!-- start of slide 34 -->
        <div class="slide" id="slide-34">
          <header>Some examples</header>

          <section>
            <p>
            Learn concurrent Go by osmosis.<br>
            
            <br>
            </p>
            



            <p>
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 34 --><!-- start of slide 35 -->
        <div class="slide" id="slide-35">
          <header>Launching daemons</header>

          <section>
            <p>
            Use a closure to wrap a background operation.<br>
            
            <br>
            
            This copies items from the input channel to the output channel.<br>
            </p>
            


<pre>
<!--{{code "concur/snippets" `/copy.input/` `/^}/`}}
-->go func() { // copy input to output
    for val := range input {
        output &lt;- val
    }
}()
</pre>


            <p>
            The for range operation runs until channel is drained.<br>
            
            <br>
            
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 35 --><!-- start of slide 36 -->
        <div class="slide" id="slide-36">
          <header>A simple load balancer (1)</header>

          <section>
            <p>
            A unit of work:<br>
            
            <br>
            </p>
            


<pre>
<!--{{code "concur/load1" `/type/` `/^}/`}}
-->type Work struct {
    x, y, z int
}
</pre>


            <p>
            <br>
            
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 36 --><!-- start of slide 37 -->
        <div class="slide" id="slide-37">
          <header>A simple load balancer (2)</header>

          <section>
            <p>
            A worker task:<br>
            </p>
            


<pre>
<!--{{code "concur/load1" `/worker/` `/^}/`}}
-->func worker(in &lt;-chan *Work, out chan&lt;- *Work) {
   for w := range in {
      w.z = w.x * w.y
      Sleep(w.z)
      out &lt;- w
   }
}
</pre>


            <p>
            Must make sure other workers can run when one blocks.<br>
            
            <br>
            
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 37 --><!-- start of slide 38 -->
        <div class="slide" id="slide-38">
          <header>A simple load balancer (3)</header>

          <section>
            <p>
            The runner:<br>
            </p>
            


<pre>
<!--{{code "concur/load1" `/Run/` `/^}/`}}
-->func Run() {
   in, out := make(chan *Work), make(chan *Work)
   for i := 0; i &lt; NumWorkers; i++ {
       go worker(in, out)
   }
   go sendLotsOfWork(in)
   receiveLotsOfResults(out)
}
</pre>


            <p>
            <br>
            
            Easy problem but also hard to solve concisely without concurrency.<br>
            
            <br>
            
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 38 --><!-- start of slide 39 -->
        <div class="slide" id="slide-39">
          <header>Concurrency enables parallelism</header>

          <section>
            <p>
            The load balancer is implicitly parallel and scalable.<br>
            
            <br>
            
            NumWorkers could be huge.<br>
            
            <br>
            
            The tools of concurrency make it almost trivial to build a safe, working, scalable, parallel design.<br>
            
            <br>
            </p>
            



            <p>
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 39 --><!-- start of slide 40 -->
        <div class="slide" id="slide-40">
          <header>Concurrency simplifies synchronization</header>

          <section>
            <p>
            No explicit synchronization needed.<br>
            
            <br>
            
            The structure of the program is implicitly synchronized.<br>
            
            <br>
            </p>
            



            <p>
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 40 --><!-- start of slide 41 -->
        <div class="slide" id="slide-41">
          <header>That was too easy</header>

          <section>
            <p>
            Let&#39;s do a more realistic load balancer.<br>
            
            <br>
            </p>
            



            <p>
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 41 --><!-- start of slide 42 -->
        <div class="slide" id="slide-42">
          <header>Load balancer</header>

          <section>
            <p></p>
            



<img src="concur/gopherchart.jpg" >

            <p>
            <br>
            
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 42 --><!-- start of slide 43 -->
        <div class="slide" id="slide-43">
          <header>Request definition</header>

          <section>
            <p>
            The requester sends Requests to the balancer.<br>
            </p>
            


<pre>
<!--{{code "concur/load2" `/^type.Request/` `/^}/`}}
-->type Request struct {
    fn func() int  // The operation to perform.
    c  chan int    // The channel to return the result.
}
</pre>


            <p>
            Note the return channel inside the request.<br>
            
            Channels are first-class values.<br>
            
            <br>
            
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 43 --><!-- start of slide 44 -->
        <div class="slide" id="slide-44">
          <header>Requester function</header>

          <section>
            <p>
            An artificial but illustrative simulation of a requester, a load generator.<br>
            
            <br>
            </p>
            


<pre>
<!--{{code "concur/load2" `/^func.requester/` `/^}/`}}
-->func requester(work chan&lt;- Request) {
    c := make(chan int)
    for {
        // Kill some time (fake load).
        Sleep(rand.Int63n(nWorker * 2 * Second))
        work &lt;- Request{workFn, c} // send request
        result := &lt;-c              // wait for answer
        furtherProcess(result)  
    }    
}
</pre>


            <p>
            <br>
            
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 44 --><!-- start of slide 45 -->
        <div class="slide" id="slide-45">
          <header>Worker definition</header>

          <section>
            <p>
            A channel of requests, plus some load tracking data.<br>
            
            <br>
            </p>
            


<pre>
<!--{{code "concur/load2" `/type.Worker/` `/^}/`}}
-->type Worker struct {
    requests chan Request // work to do (buffered channel)
    pending  int          // count of pending tasks
    index     int         // index in the heap
}
</pre>


            <p>
            <br>
            
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 45 --><!-- start of slide 46 -->
        <div class="slide" id="slide-46">
          <header>Worker</header>

          <section>
            <p>
            Balancer sends request to most lightly loaded worker.<br>
            </p>
            


<pre>
<!--{{code "concur/load2" `/^func.*work.*done/` `/^}/`}}
-->func (w *Worker) work(done chan *Worker) {
    for {
        req := &lt;-w.requests // get Request from balancer
        req.c &lt;- req.fn()   // call fn and send result
        done &lt;- w           // we&#39;ve finished this request
    }
}
</pre>


            <p>
            The channel of requests (w.requests) delivers requests to each worker.  The balancer tracks the number of pending requests as a measure of load.<br>
            
            Each response goes directly to its requester.<br>
            
            <br>
            
            Could run the loop body as a goroutine for parallelism.<br>
            
            <br>
            
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 46 --><!-- start of slide 47 -->
        <div class="slide" id="slide-47">
          <header>Balancer definition</header>

          <section>
            <p>
            The load balancer needs a pool of workers and a single channel to which requesters can report task completion.<br>
            
            <br>
            </p>
            


<pre>
<!--{{code "concur/load2" `/type.Pool/` `/^}/`}}
-->type Pool []*Worker

type Balancer struct {
    pool Pool
    done chan *Worker
}
</pre>


            <p>
            <br>
            
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 47 --><!-- start of slide 48 -->
        <div class="slide" id="slide-48">
          <header>Balancer function</header>

          <section>
            <p>
            Easy!<br>
            
            <br>
            </p>
            


<pre>
<!--{{code "concur/load2" `/func.*balance/` `/^}/`}}
-->func (b *Balancer) balance(work chan Request) {
    for {
        select {
        case req := &lt;-work: // received a Request...
            b.dispatch(req) // ...so send it to a Worker
        case w := &lt;-b.done: // a worker has finished ...
            b.completed(w)  // ...so update its info
        }
    }
}
</pre>


            <p>
            <br>
            
            Just need to implement dispatch and completed.<br>
            
            <br>
            
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 48 --><!-- start of slide 49 -->
        <div class="slide" id="slide-49">
          <header>A heap of channels</header>

          <section>
            <p>
            Make Pool an implementation of the Heap interface by providing a few methods such as:<br>
            
            <br>
            </p>
            


<pre>
<!--{{code "concur/load2" `/func.*Less/` `/^}/`}}
-->func (p Pool) Less(i, j int) bool {
    return p[i].pending &lt; p[j].pending
}
</pre>


            <p>
            <br>
            
            Now we balance by making the Pool a heap tracked by load.<br>
            
            <br>
            
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 49 --><!-- start of slide 50 -->
        <div class="slide" id="slide-50">
          <header>Dispatch</header>

          <section>
            <p>
            All the pieces are in place.<br>
            
            <br>
            </p>
            


<pre>
<!--{{code "concur/load2" `/Send.Request/` `/^}/`}}
-->// Send Request to worker
func (b *Balancer) dispatch(req Request) {
    // Grab the least loaded worker...
    w := heap.Pop(&amp;b.pool).(*Worker)
    // ...send it the task.
    w.requests &lt;- req
    // One more in its work queue.
    w.pending++
    // Put it into its place on the heap.
    heap.Push(&amp;b.pool, w)
}
</pre>


            <p>
            <br>
            
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 50 --><!-- start of slide 51 -->
        <div class="slide" id="slide-51">
          <header>Completed</header>

          <section>
            <p></p>
            


<pre>
<!--{{code "concur/load2" `/Job.is.complete/` `/^}/`}}
-->// Job is complete; update heap
func (b *Balancer) completed(w *Worker) {
    // One fewer in the queue.
    w.pending--
    // Remove it from heap.                  
    heap.Remove(&amp;b.pool, w.index)
    // Put it into its place on the heap.
    heap.Push(&amp;b.pool, w)
}
</pre>


            <p>
            <br>
            
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 51 --><!-- start of slide 52 -->
        <div class="slide" id="slide-52">
          <header>Lesson</header>

          <section>
            <p>
            A complex problem can be broken down into easy-to-understand components.<br>
            
            <br>
            
            The pieces can be composed concurrently.<br>
            
            <br>
            
            The result is easy to understand, efficient, scalable, and correct.<br>
            
            <br>
            
            Maybe even parallel.<br>
            
            <br>
            </p>
            



            <p>
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 52 --><!-- start of slide 53 -->
        <div class="slide" id="slide-53">
          <header>One more example</header>

          <section>
            <p>
            We have a replicated database and want to minimize latency by asking them all and returning the first response to arrive.<br>
            
            <br>
            </p>
            



            <p>
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 53 --><!-- start of slide 54 -->
        <div class="slide" id="slide-54">
          <header>Query a replicated database</header>

          <section>
            <p></p>
            


<pre>
<!--{{code "concur/snippets" `/func.Query/` `/^}/`}}
-->func Query(conns []Conn, query string) Result {
    ch := make(chan Result, len(conns))  // buffered
    for _, conn := range conns {
        go func(c Conn) {
            ch &lt;- c.DoQuery(query):
        }(conn)
    }
    return &lt;-ch
}
</pre>


            <p>
            Concurrent tools and garbage collection make this an easy solution to a subtle problem.<br>
            
            <br>
            
            (Teardown of late finishers is left as an exercise.)<br>
            
            <br>
            
            <br>
            
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 54 --><!-- start of slide 55 -->
        <div class="slide" id="slide-55">
          <header>Conclusion</header>

          <section>
            <p>
            Concurrency is powerful.<br>
            
            <br>
            
            Concurrency is not parallelism.<br>
            
            <br>
            
            Concurrency enables parallelism.<br>
            
            <br>
            
            Concurrency makes parallelism (and scaling and everything else) easy.<br>
            
            <br>
            </p>
            



            <p>
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 55 --><!-- start of slide 56 -->
        <div class="slide" id="slide-56">
          <header>For more information</header>

          <section>
            <p>
            Go: golang.org<br>
            
            <br>
            
            Some history: swtch.com/~rsc/thread/<br>
            
            <br>
            
            A previous talk (video): tinyurl.com/newsqueak<br>
            
            <br>
            
            Parellelism is not concurrency (Harper): tinyurl.com/pincharper<br>
            
            <br>
            
            A concurrent window system (Pike): tinyurl.com/pikecws<br>
            
            <br>
            
            Concurrent power series (McIlroy): tinyurl.com/powser<br>
            
            <br>
            
            And finally, parallel but not concurrent:<br>
            
            research.google.com/archive/sawzall.html<br>
            </p>
            



            <p>
          </section>
        </div> <!-- end slide template -->
      <!-- end of slide 56 -->

        <div class="slide" id="goodbye">
          <section class="middle">
            <hgroup><img src="http://golang.org/doc/gopher/bumper640x360.png"></hgroup>
          </section>
        </div>

      </div>

      <div id="speaker-note" class="invisible" style="display: none;">
      </div> <!-- speaker note -->
      <aside id="help" class="sidebar invisible" style="display: hidden;">
        <table>
          <caption>Help</caption>
          <tbody>
            <tr>
              <th>Move Around</th>
              <td>&larr;&nbsp;&rarr;</td>
            </tr>
            <tr>
              <th>Source File</th>
              <td>s</td>
            </tr>
            <tr>
              <th>Speaker Notes</th>
              <td>n</td>
            </tr>
            <tr>
              <th>Toggle 3D</th>
              <td>3</td>
            </tr>
            <tr>
              <th>Help</th>
              <td>0</td>
            </tr>
          </tbody>
        </table>
      </aside>

    </div> <!-- presentation -->

    <!--[if lt IE 9]>
    <script 
      src="http://ajax.googleapis.com/ajax/libs/chrome-frame/1/CFInstall.min.js">
    </script>
    <script>CFInstall.check({ mode: "overlay" });</script>
    <![endif]-->

    <script src="js/utils.js"></script>
  </body>
</html>
